package org.example;

public class Test1 {
    //leetcode 718 最长重复子数组 https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
    public int findLength(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        //dp[i][j]表示nums1数组以i位置为结尾的子数组和nums2数组以j位置为结尾的子数组的最长重复子数组
        int[][] dp = new int[n1+1][n2+1];
        int ret = 0;
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                dp[i][j] = nums1[i-1] == nums2[j-1] ? dp[i-1][j-1] + 1 : 0;
                ret = Math.max(ret,dp[i][j]);
            }
        }
        return ret;
    }

    //优化
    public int findLength1(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int[] dp = new int[n2+1];
        int ret = 0;
        for (int i = 1; i <= n1; i++) {
            for (int j = n2; j >= 1; j--) {
                dp[j] = nums1[i-1] == nums2[j-1] ? dp[j-1] + 1 : 0;
                ret = Math.max(ret,dp[j]);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] arr1 = {1,2,3,2,1};
        int[] arr2 = {3,2,1,4,7};
        Test1 test1 = new Test1();
        test1.findLength(arr1,arr2);
        System.out.println(555);
    }
}
